#include <cstdio>

int cnt[ 21 ][ 21 ][ 21 ], n, m;
bool map[ 21 ][ 21 ];

void init( )
{
    int i, j, k, a, b;
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < n; j++ )
        {
            map[ i ][ j ] = false;
            for ( k = 0; k <= 20; k++ )
                cnt[ i ][ j ][ k ] = 0;
        }
    for ( i = 0; i < n; i++ )
        cnt[ i ][ i ][ 0 ] = 1;
    for ( i = 0; i < m; i++ )
    {
        scanf("%d%d", &a, &b);
        if ( a != b )
        {
            cnt[ a ][ b ][ 1 ] = 1;
            map[ a ][ b ] = true;
        }
    }
}

void work( )
{
    int t, i, j, p, A, B, k;
    for ( k = 2; k <= 20; k++ )
        for ( p = 0; p < n; p++ )
            for ( i = 0; i < n; i++ )
                for ( j = 0; j < n; j++ )
                    if ( map[ p ][ j ] )
                        cnt[ i ][ j ][ k ] = ( cnt[ i ][ j ][ k ] + cnt[ i ][ p ][ k - 1 ] ) % 1000;
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d%d%d", &A, &B, &k);
        printf("%d\n", cnt[ A ][ B ][ k ]);
    }
}

int main( )
{
    while ( scanf("%d%d", &n, &m) != EOF )
    {
        if ( n == 0 && m == 0 )
            break;
        init( );
        work( );
    }
    return 0;
}
